package 剑指II;

import java.util.HashSet;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-02
 **/

public class Jz014字符串中的变位词 {

    /**
     * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
     * 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
     * <p>
     * 示例 1：
     * 输入: s1 = "ab" s2 = "eidbaooo"
     * 输出: True
     * 解释: s2 包含 s1 的排列之一 ("ba").
     * 示例 2：
     * 输入: s1= "ab" s2 = "eidboaoo"
     * 输出: False
     *  
     * 提示：
     * 1 <= s1.length, s2.length <= 104
     * s1 和 s2 仅包含小写字母
     */

    public boolean checkInclusion(String s1, String s2) {

        int left = 0;
        int right = 0;
        char[] smallArr = s1.toCharArray();
        char[] bigArr = s2.toCharArray();
        Set<Character> set = new HashSet<>();

        int sourceCount = 0;
        int count = 0;
        int[] arr = new int[26];
        for (char c : smallArr) {
            if (arr[c - 'a'] == 0) {
                count++;
            }
            arr[c - 'a']++;
            set.add(c);
        }
        sourceCount = count;

        while (right < bigArr.length && count != 0) {

            char c = bigArr[right];

            if (!set.contains(c)) {
                while (left < right) {
                    arr[bigArr[left++] - 'a']++;
                }
                right++;
                left = right;
                count = sourceCount;
                continue;
            }

            while (left < right && arr[c - 'a'] == 0) {
                char lC = bigArr[left++];
                if (arr[lC - 'a'] == 0) {
                    count++;
                }
                arr[lC - 'a']++;
            }

            arr[c - 'a']--;
            if (arr[c - 'a'] == 0) {
                count--;
            }

            right++;
        }

        return count == 0;
    }

    public static void main(String[] args) {
        Jz014字符串中的变位词 n = new Jz014字符串中的变位词();
        boolean result = n.checkInclusion("a", "b");
        System.out.println(result);
    }

}
